package com.yequan.leetcode.algorithm.search.BinarySearch.mySqrt_69;

/**
 * //实现 int sqrt(int x) 函数。
 * //
 * // 计算并返回 x 的平方根，其中 x 是非负整数。
 * //
 * // 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 * //
 * // 示例 1:
 * //
 * // 输入: 4
 * //输出: 2
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: 8
 * //输出: 2
 * //说明: 8 的平方根是 2.82842...,
 * //     由于返回类型是整数，小数部分将被舍去。
 * //
 * // Related Topics 数学 二分查找
 *
 * @author : Administrator
 * @date : 2020/4/5
 */
public class MySqrt {

    public static void main(String[] args) {
        MySqrt mySqrt = new MySqrt();
        int sqrt = mySqrt.mySqrt1(2147395599);
        System.out.println(sqrt);
    }

    /**
     * 二分法
     * 注意需要使用 long类型的 要不然 mid*mid会超出int的最大值
     * <p>
     * 最后结果取right是因为当 x>=2时, (x/2)的平方一定大于 x ,所以一定是右边界缩小,最终是取right
     *
     * @param x
     * @return
     */
    public int mySqrt1(int x) {
        if (x < 2) {
            return x;
        }
        long left = 1;
        long right = x >> 1;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            if (mid * mid == x) {
                return (int) mid;
            } else if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (int) right;
    }

    /**
     * 牛顿迭代法
     *
     * @param x
     * @return
     */
    public int mySqrt2(int x) {
        long sqrt = x;
        while (sqrt * sqrt > x) {
            sqrt = (sqrt + (x / sqrt)) / 2;
        }
        return (int) sqrt;
    }

}
